1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 package com.google.common.collect;
16
17 import static com.google.common.truth.Truth.assertThat;
18
19 import com.google.common.annotations.GwtIncompatible;
20 import com.google.common.collect.testing.NavigableSetTestSuiteBuilder;
21 import com.google.common.collect.testing.SampleElements;
22 import com.google.common.collect.testing.TestSetGenerator;
23 import com.google.common.collect.testing.features.CollectionFeature;
24 import com.google.common.collect.testing.features.CollectionSize;
25 import com.google.common.testing.SerializableTester;
26
27 import junit.framework.Test;
28 import junit.framework.TestSuite;
29
30 import java.math.BigInteger;
31 import java.util.List;
32 import java.util.Set;
33
34
35
36
37
38
39 @GwtIncompatible("ImmutableRangeSet")
40 public class ImmutableRangeSetTest extends AbstractRangeSetTest {
41 @SuppressWarnings("unchecked")
42 private static final ImmutableSet<Range<Integer>> RANGES = ImmutableSet.of(
43 Range.<Integer>all(),
44 Range.closedOpen(3, 5),
45 Range.singleton(1),
46 Range.lessThan(2),
47 Range.greaterThan(10),
48 Range.atMost(4),
49 Range.atLeast(3),
50 Range.closed(4, 6),
51 Range.closedOpen(1, 3),
52 Range.openClosed(5, 7),
53 Range.open(3, 4));
54
55 static final class ImmutableRangeSetIntegerAsSetGenerator implements TestSetGenerator<Integer> {
56 @Override
57 public SampleElements<Integer> samples() {
58 return new SampleElements<Integer>(1, 4, 3, 2, 5);
59 }
60
61 @Override
62 public Integer[] createArray(int length) {
63 return new Integer[length];
64 }
65
66 @Override
67 public Iterable<Integer> order(List<Integer> insertionOrder) {
68 return Ordering.natural().sortedCopy(insertionOrder);
69 }
70
71 @Override
72 public Set<Integer> create(Object... elements) {
73 ImmutableRangeSet.Builder<Integer> builder = ImmutableRangeSet.builder();
74 for (Object o : elements) {
75 Integer i = (Integer) o;
76 builder.add(Range.singleton(i));
77 }
78 return builder.build().asSet(DiscreteDomain.integers());
79 }
80 }
81
82 static final class ImmutableRangeSetBigIntegerAsSetGenerator
83 implements TestSetGenerator<BigInteger> {
84 @Override
85 public SampleElements<BigInteger> samples() {
86 return new SampleElements<BigInteger>(
87 BigInteger.valueOf(1),
88 BigInteger.valueOf(4),
89 BigInteger.valueOf(3),
90 BigInteger.valueOf(2),
91 BigInteger.valueOf(5));
92 }
93
94 @Override
95 public BigInteger[] createArray(int length) {
96 return new BigInteger[length];
97 }
98
99 @Override
100 public Iterable<BigInteger> order(List<BigInteger> insertionOrder) {
101 return Ordering.natural().sortedCopy(insertionOrder);
102 }
103
104 @Override
105 public Set<BigInteger> create(Object... elements) {
106 ImmutableRangeSet.Builder<BigInteger> builder = ImmutableRangeSet.builder();
107 for (Object o : elements) {
108 BigInteger i = (BigInteger) o;
109 builder.add(Range.closedOpen(i, i.add(BigInteger.ONE)));
110 }
111 return builder.build().asSet(DiscreteDomain.bigIntegers());
112 }
113 }
114
115 public static Test suite() {
116 TestSuite suite = new TestSuite();
117 suite.addTestSuite(ImmutableRangeSetTest.class);
118 suite.addTest(NavigableSetTestSuiteBuilder.using(new ImmutableRangeSetIntegerAsSetGenerator())
119 .named("ImmutableRangeSet.asSet[DiscreteDomain.integers[]]")
120 .withFeatures(
121 CollectionSize.ANY,
122 CollectionFeature.REJECTS_DUPLICATES_AT_CREATION,
123 CollectionFeature.ALLOWS_NULL_QUERIES,
124 CollectionFeature.KNOWN_ORDER,
125 CollectionFeature.NON_STANDARD_TOSTRING,
126 CollectionFeature.SERIALIZABLE)
127 .createTestSuite());
128
129 suite.addTest(NavigableSetTestSuiteBuilder.using(
130 new ImmutableRangeSetBigIntegerAsSetGenerator())
131 .named("ImmutableRangeSet.asSet[DiscreteDomain.bigIntegers[]]")
132 .withFeatures(
133 CollectionSize.ANY,
134 CollectionFeature.REJECTS_DUPLICATES_AT_CREATION,
135 CollectionFeature.ALLOWS_NULL_QUERIES,
136 CollectionFeature.KNOWN_ORDER,
137 CollectionFeature.NON_STANDARD_TOSTRING,
138 CollectionFeature.SERIALIZABLE)
139 .createTestSuite());
140 return suite;
141 }
142
143 public void testEmpty() {
144 ImmutableRangeSet<Integer> rangeSet = ImmutableRangeSet.of();
145
146 assertThat(rangeSet.asRanges()).isEmpty();
147 assertEquals(ImmutableRangeSet.<Integer>all(), rangeSet.complement());
148 assertFalse(rangeSet.contains(0));
149 assertFalse(rangeSet.encloses(Range.singleton(0)));
150 assertTrue(rangeSet.enclosesAll(rangeSet));
151 assertTrue(rangeSet.isEmpty());
152 }
153
154 public void testAll() {
155 ImmutableRangeSet<Integer> rangeSet = ImmutableRangeSet.all();
156
157 assertThat(rangeSet.asRanges()).has().item(Range.<Integer>all());
158 assertTrue(rangeSet.contains(0));
159 assertTrue(rangeSet.encloses(Range.<Integer>all()));
160 assertTrue(rangeSet.enclosesAll(rangeSet));
161 assertEquals(ImmutableRangeSet.<Integer>of(), rangeSet.complement());
162 }
163
164 public void testSingleBoundedRange() {
165 ImmutableRangeSet<Integer> rangeSet = ImmutableRangeSet.of(Range.closedOpen(1, 5));
166
167 assertThat(rangeSet.asRanges()).has().item(Range.closedOpen(1, 5));
168
169 assertTrue(rangeSet.encloses(Range.closed(3, 4)));
170 assertTrue(rangeSet.encloses(Range.closedOpen(1, 4)));
171 assertTrue(rangeSet.encloses(Range.closedOpen(1, 5)));
172 assertFalse(rangeSet.encloses(Range.greaterThan(2)));
173
174 assertTrue(rangeSet.contains(3));
175 assertFalse(rangeSet.contains(5));
176 assertFalse(rangeSet.contains(0));
177
178 RangeSet<Integer> expectedComplement = TreeRangeSet.create();
179 expectedComplement.add(Range.lessThan(1));
180 expectedComplement.add(Range.atLeast(5));
181
182 assertEquals(expectedComplement, rangeSet.complement());
183 }
184
185 public void testSingleBoundedBelowRange() {
186 ImmutableRangeSet<Integer> rangeSet = ImmutableRangeSet.of(Range.greaterThan(2));
187
188 assertThat(rangeSet.asRanges()).has().item(Range.greaterThan(2));
189
190 assertTrue(rangeSet.encloses(Range.closed(3, 4)));
191 assertTrue(rangeSet.encloses(Range.greaterThan(3)));
192 assertFalse(rangeSet.encloses(Range.closedOpen(1, 5)));
193
194 assertTrue(rangeSet.contains(3));
195 assertTrue(rangeSet.contains(5));
196 assertFalse(rangeSet.contains(0));
197 assertFalse(rangeSet.contains(2));
198
199 assertEquals(ImmutableRangeSet.of(Range.atMost(2)), rangeSet.complement());
200 }
201
202 public void testSingleBoundedAboveRange() {
203 ImmutableRangeSet<Integer> rangeSet = ImmutableRangeSet.of(Range.atMost(3));
204
205 assertThat(rangeSet.asRanges()).has().item(Range.atMost(3));
206
207 assertTrue(rangeSet.encloses(Range.closed(2, 3)));
208 assertTrue(rangeSet.encloses(Range.lessThan(1)));
209 assertFalse(rangeSet.encloses(Range.closedOpen(1, 5)));
210
211 assertTrue(rangeSet.contains(3));
212 assertTrue(rangeSet.contains(0));
213 assertFalse(rangeSet.contains(4));
214 assertFalse(rangeSet.contains(5));
215
216 assertEquals(ImmutableRangeSet.of(Range.greaterThan(3)), rangeSet.complement());
217 }
218
219 public void testMultipleBoundedRanges() {
220 ImmutableRangeSet<Integer> rangeSet = ImmutableRangeSet.<Integer>builder()
221 .add(Range.closed(5, 8)).add(Range.closedOpen(1, 3)).build();
222
223 assertThat(rangeSet.asRanges())
224 .has().exactly(Range.closedOpen(1, 3), Range.closed(5, 8)).inOrder();
225
226 assertTrue(rangeSet.encloses(Range.closed(1, 2)));
227 assertTrue(rangeSet.encloses(Range.open(5, 8)));
228 assertFalse(rangeSet.encloses(Range.closed(1, 8)));
229 assertFalse(rangeSet.encloses(Range.greaterThan(5)));
230
231 RangeSet<Integer> expectedComplement = ImmutableRangeSet.<Integer>builder()
232 .add(Range.lessThan(1))
233 .add(Range.closedOpen(3, 5))
234 .add(Range.greaterThan(8))
235 .build();
236
237 assertEquals(expectedComplement, rangeSet.complement());
238 }
239
240 public void testMultipleBoundedBelowRanges() {
241 ImmutableRangeSet<Integer> rangeSet = ImmutableRangeSet.<Integer>builder()
242 .add(Range.greaterThan(6)).add(Range.closedOpen(1, 3)).build();
243
244 assertThat(rangeSet.asRanges())
245 .has().exactly(Range.closedOpen(1, 3), Range.greaterThan(6)).inOrder();
246
247 assertTrue(rangeSet.encloses(Range.closed(1, 2)));
248 assertTrue(rangeSet.encloses(Range.open(6, 8)));
249 assertFalse(rangeSet.encloses(Range.closed(1, 8)));
250 assertFalse(rangeSet.encloses(Range.greaterThan(5)));
251
252 RangeSet<Integer> expectedComplement = ImmutableRangeSet.<Integer>builder()
253 .add(Range.lessThan(1))
254 .add(Range.closed(3, 6))
255 .build();
256
257 assertEquals(expectedComplement, rangeSet.complement());
258 }
259
260 public void testMultipleBoundedAboveRanges() {
261 ImmutableRangeSet<Integer> rangeSet = ImmutableRangeSet.<Integer>builder()
262 .add(Range.atMost(0)).add(Range.closedOpen(2, 5)).build();
263
264 assertThat(rangeSet.asRanges())
265 .has().exactly(Range.atMost(0), Range.closedOpen(2, 5)).inOrder();
266
267 assertTrue(rangeSet.encloses(Range.closed(2, 4)));
268 assertTrue(rangeSet.encloses(Range.open(-5, -2)));
269 assertFalse(rangeSet.encloses(Range.closed(1, 8)));
270 assertFalse(rangeSet.encloses(Range.greaterThan(5)));
271
272 RangeSet<Integer> expectedComplement = ImmutableRangeSet.<Integer>builder()
273 .add(Range.open(0, 2))
274 .add(Range.atLeast(5))
275 .build();
276
277 assertEquals(expectedComplement, rangeSet.complement());
278 }
279
280 public void testAddUnsupported() {
281 ImmutableRangeSet<Integer> rangeSet = ImmutableRangeSet.<Integer>builder()
282 .add(Range.closed(5, 8)).add(Range.closedOpen(1, 3)).build();
283
284 try {
285 rangeSet.add(Range.open(3, 4));
286 fail();
287 } catch (UnsupportedOperationException expected) {
288
289 }
290 }
291
292 public void testAddAllUnsupported() {
293 ImmutableRangeSet<Integer> rangeSet = ImmutableRangeSet.<Integer>builder()
294 .add(Range.closed(5, 8)).add(Range.closedOpen(1, 3)).build();
295
296 try {
297 rangeSet.addAll(ImmutableRangeSet.<Integer>of());
298 fail();
299 } catch (UnsupportedOperationException expected) {
300
301 }
302 }
303
304 public void testRemoveUnsupported() {
305 ImmutableRangeSet<Integer> rangeSet = ImmutableRangeSet.<Integer>builder()
306 .add(Range.closed(5, 8)).add(Range.closedOpen(1, 3)).build();
307
308 try {
309 rangeSet.remove(Range.closed(6, 7));
310 fail();
311 } catch (UnsupportedOperationException expected) {
312
313 }
314 }
315
316 public void testRemoveAllUnsupported() {
317 ImmutableRangeSet<Integer> rangeSet = ImmutableRangeSet.<Integer>builder()
318 .add(Range.closed(5, 8)).add(Range.closedOpen(1, 3)).build();
319
320 try {
321 rangeSet.removeAll(ImmutableRangeSet.<Integer>of());
322 fail();
323 } catch (UnsupportedOperationException expected) {
324
325 }
326
327 try {
328 rangeSet.removeAll(ImmutableRangeSet.of(Range.closed(6, 8)));
329 fail();
330 } catch (UnsupportedOperationException expected) {
331
332 }
333 }
334
335 public void testExhaustive() {
336 @SuppressWarnings("unchecked")
337 ImmutableSet<Range<Integer>> ranges = ImmutableSet.of(
338 Range.<Integer>all(),
339 Range.<Integer>closedOpen(3, 5),
340 Range.singleton(1),
341 Range.lessThan(2),
342 Range.greaterThan(10),
343 Range.atMost(4),
344 Range.atLeast(3),
345 Range.closed(4, 6),
346 Range.closedOpen(1, 3),
347 Range.openClosed(5, 7),
348 Range.open(3, 4));
349 for (Set<Range<Integer>> subset : Sets.powerSet(ranges)) {
350 RangeSet<Integer> mutable = TreeRangeSet.create();
351 ImmutableRangeSet.Builder<Integer> builder = ImmutableRangeSet.builder();
352
353 int expectedRanges = 0;
354 for (Range<Integer> range : subset) {
355 boolean overlaps = false;
356 for (Range<Integer> other : mutable.asRanges()) {
357 if (other.isConnected(range) && !other.intersection(range).isEmpty()) {
358 overlaps = true;
359 }
360 }
361
362 try {
363 builder.add(range);
364 assertFalse(overlaps);
365 mutable.add(range);
366 } catch (IllegalArgumentException e) {
367 assertTrue(overlaps);
368 }
369 }
370
371 ImmutableRangeSet<Integer> built = builder.build();
372 assertEquals(mutable, built);
373 assertEquals(ImmutableRangeSet.copyOf(mutable), built);
374 assertEquals(mutable.complement(), built.complement());
375
376 for (int i = 0; i <= 11; i++) {
377 assertEquals(mutable.contains(i), built.contains(i));
378 }
379
380 SerializableTester.reserializeAndAssert(built);
381 }
382 }
383
384 public void testAsSet() {
385 ImmutableRangeSet<Integer> rangeSet = ImmutableRangeSet.<Integer>builder()
386 .add(Range.closed(2, 4))
387 .add(Range.open(6, 7))
388 .add(Range.closedOpen(8, 10))
389 .add(Range.openClosed(15, 17))
390 .build();
391 ImmutableSortedSet<Integer> expectedSet = ImmutableSortedSet.of(2, 3, 4, 8, 9, 16, 17);
392 ImmutableSortedSet<Integer> asSet = rangeSet.asSet(DiscreteDomain.integers());
393 assertEquals(expectedSet, asSet);
394 assertThat(asSet).has().exactlyAs(expectedSet).inOrder();
395 assertTrue(asSet.containsAll(expectedSet));
396 SerializableTester.reserializeAndAssert(asSet);
397 }
398
399 public void testAsSetHeadSet() {
400 ImmutableRangeSet<Integer> rangeSet = ImmutableRangeSet.<Integer>builder()
401 .add(Range.closed(2, 4))
402 .add(Range.open(6, 7))
403 .add(Range.closedOpen(8, 10))
404 .add(Range.openClosed(15, 17))
405 .build();
406
407 ImmutableSortedSet<Integer> expectedSet = ImmutableSortedSet.of(2, 3, 4, 8, 9, 16, 17);
408 ImmutableSortedSet<Integer> asSet = rangeSet.asSet(DiscreteDomain.integers());
409
410 for (int i = 0; i <= 20; i++) {
411 assertEquals(asSet.headSet(i, false), expectedSet.headSet(i, false));
412 assertEquals(asSet.headSet(i, true), expectedSet.headSet(i, true));
413 }
414 }
415
416 public void testAsSetTailSet() {
417 ImmutableRangeSet<Integer> rangeSet = ImmutableRangeSet.<Integer>builder()
418 .add(Range.closed(2, 4))
419 .add(Range.open(6, 7))
420 .add(Range.closedOpen(8, 10))
421 .add(Range.openClosed(15, 17))
422 .build();
423
424 ImmutableSortedSet<Integer> expectedSet = ImmutableSortedSet.of(2, 3, 4, 8, 9, 16, 17);
425 ImmutableSortedSet<Integer> asSet = rangeSet.asSet(DiscreteDomain.integers());
426
427 for (int i = 0; i <= 20; i++) {
428 assertEquals(asSet.tailSet(i, false), expectedSet.tailSet(i, false));
429 assertEquals(asSet.tailSet(i, true), expectedSet.tailSet(i, true));
430 }
431 }
432
433 public void testAsSetSubSet() {
434 ImmutableRangeSet<Integer> rangeSet = ImmutableRangeSet.<Integer>builder()
435 .add(Range.closed(2, 4))
436 .add(Range.open(6, 7))
437 .add(Range.closedOpen(8, 10))
438 .add(Range.openClosed(15, 17))
439 .build();
440
441 ImmutableSortedSet<Integer> expectedSet = ImmutableSortedSet.of(2, 3, 4, 8, 9, 16, 17);
442 ImmutableSortedSet<Integer> asSet = rangeSet.asSet(DiscreteDomain.integers());
443
444 for (int i = 0; i <= 20; i++) {
445 for (int j = i + 1; j <= 20; j++) {
446 assertEquals(expectedSet.subSet(i, false, j, false),
447 asSet.subSet(i, false, j, false));
448 assertEquals(expectedSet.subSet(i, true, j, false),
449 asSet.subSet(i, true, j, false));
450 assertEquals(expectedSet.subSet(i, false, j, true),
451 asSet.subSet(i, false, j, true));
452 assertEquals(expectedSet.subSet(i, true, j, true),
453 asSet.subSet(i, true, j, true));
454 }
455 }
456 }
457
458 public void testSubRangeSet() {
459 ImmutableList.Builder<Range<Integer>> rangesBuilder = ImmutableList.builder();
460 rangesBuilder.add(Range.<Integer>all());
461 for (int i = -2; i <= 2; i++) {
462 for (BoundType boundType : BoundType.values()) {
463 rangesBuilder.add(Range.upTo(i, boundType));
464 rangesBuilder.add(Range.downTo(i, boundType));
465 }
466 for (int j = i + 1; j <= 2; j++) {
467 for (BoundType lbType : BoundType.values()) {
468 for (BoundType ubType : BoundType.values()) {
469 rangesBuilder.add(Range.range(i, lbType, j, ubType));
470 }
471 }
472 }
473 }
474 ImmutableList<Range<Integer>> ranges = rangesBuilder.build();
475 for (int i = -2; i <= 2; i++) {
476 rangesBuilder.add(Range.closedOpen(i, i));
477 rangesBuilder.add(Range.openClosed(i, i));
478 }
479 ImmutableList<Range<Integer>> subRanges = rangesBuilder.build();
480 for (Range<Integer> range1 : ranges) {
481 for (Range<Integer> range2 : ranges) {
482 if (!range1.isConnected(range2) || range1.intersection(range2).isEmpty()) {
483 ImmutableRangeSet<Integer> rangeSet = ImmutableRangeSet.<Integer>builder()
484 .add(range1)
485 .add(range2)
486 .build();
487 for (Range<Integer> subRange : subRanges) {
488 RangeSet<Integer> expected = TreeRangeSet.create();
489 for (Range<Integer> range : rangeSet.asRanges()) {
490 if (range.isConnected(subRange)) {
491 expected.add(range.intersection(subRange));
492 }
493 }
494 ImmutableRangeSet<Integer> subRangeSet = rangeSet.subRangeSet(subRange);
495 assertEquals(expected, subRangeSet);
496 assertEquals(expected.asRanges(), subRangeSet.asRanges());
497 if (!expected.isEmpty()) {
498 assertEquals(expected.span(), subRangeSet.span());
499 }
500 for (int i = -3; i <= 3; i++) {
501 assertEquals(expected.contains(i), subRangeSet.contains(i));
502 }
503 }
504 }
505 }
506 }
507 }
508 }